原始题目:剑指 Offer 38. 字符串的排列 (opens new window)

解题思路:

对于长度为 NN 的不重复字符串,它的排列方案有 N!N! 种。

可以采取字符交换的方式,先固定第 11 位、再固定第 22 位、……、最后固定第 nn 位。如下图:

38-abc的排列

以 "acb" 为例子,来讲述生成过程的思路。

  1. 初始时字符数组为 {'a', 'b', 'c'} ,且所有的交换都是和本身以及后面的元素交换。
  2. 固定第 11 位,第 11 位固定为 a(代码中就是 a 和 a 位置交换),剩下的可操作字符串就是 "bc"。
  3. 固定第 22 位,第 22 位可以固定为 b 或者 c (代码中就是 b 和 b 交换位置,或者 b 和 c 交换位置)
    1. 假设 b 和 c 交换位置,那么第二位固定为 c,剩下的可操作字符串就是 "b"。
  4. 固定第 33 位,第 33 位只剩下一个 b 可以选择,因此整个过程结束。此时字符数组的内容就是 {'a', 'c', 'b'} 。

**如果后面的元素有重复的话,就不需要交换了,因为会产生一个重复的结果。**因此碰到重复的元素,要跳过。

这个过程实际是一个深度优先搜索+剪枝法的结合

dfs函数

**传递参数:**当前固定位 xx

**终止条件:**当 x=len(c)1x = len(c) - 1 时,表示 xx已经时最后一个字符了,只有一种情况,因此将组合 cc 转化成字符串加入 ansans 列表。

递推工作:

  1. 初始化一个集合 setset,用来排除重复的字符串。
  2. 将第 xx 位的字符与 ii \in [x,len(c)1][x, len(c) - 1] 的字符分别交换,然后进入下一层递归
    1. 剪枝:如果 c[i]c[i]setset 中,代表这个字符已经交换过了,跳过这个字符。
    2. 交换字符:将 xx 位置和 ii 位置的字符进行交换
    3. 下一层递归:将当前位置 x+1x + 1 作为参数,传递给下一层递归。
    4. 还原字符:将 xx 位置和 ii 位置的字符再进行一次交换。
    5. c[i]c[i] 加入到 setset 中,方便后面的剪枝。

代码:

List<String> ans = new ArrayList<>();
char[] chars;

public String[] permutation(String s) {
    chars = s.toCharArray();
    dfs(0);
    return ans.toArray(new String[0]);
}

private void dfs(int x) {
    if (x == chars.length) {
        ans.add(new String(chars));
        return;
    }
    HashSet<Character> set = new HashSet<>();
    for (int i = x; i < chars.length; i++) {
        if (set.contains(chars[i])) {
            // 剪枝
            continue;
        }
        swap(i, x);
        dfs(x + 1);
        swap(i, x);
        set.add(chars[i]);
    }
}

private void swap(int i, int j) {
    char tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

复杂度分析

  • 时间复杂度O(N!N)O(N!N)NN 为字符串的长度,最坏情况下,所有字符都不相同,需要生成 N!N! 个结果,每个结果都需要使用 O(N)O(N) 的时间来拼接字符串。
  • 空间复杂度O(N2)O(N^2)NN 为字符串的长度,整个过程累计递归栈空间为 O(N)O(N);每层递归中辅助集合存储的字符串数量最多为 N+(N1)+(N2)+...+2+1=(N+1)N2N + (N-1) + (N-2) + ... + 2 + 1 = \frac{(N+1)N}{2},及占用 O(N2)O(N^2) 的空间。
上次更新: 2023/10/15